1. Field of the Invention
The present invention relates to a content-addressable memory that has storage areas each storing therein information and outputs an address (pointer) of a storage area storing therein information matching with information input from exterior.
2. Description of the Related Art
The CAM (content-addressable memory) is a memory device for searching, at high speed, for information having certain correlation with externally input information by means of hardware, and it has recently been incorporated in not only routers that perform packet routing and filtering but also Layer-4 switches that distribute requests (connection requests) from clients in Layer-4.
FIG. 5 shows the configuration of a conventional CAM. As shown in FIG. 5, a 1-bit enable signal S, data D having a prescribed word length, an address A, an instruction I, a search key K, and a control signal I/D are input to an enable terminal Sin, a data input Din, an address input Ain, an instruction input Iin, a search key input Kin, and a control terminal I/Din of a decoder 50, respectively. N decoding outputs SETout-1 to SETout-N (for the sake of simplicity, it is assumed that N is equal to 2 n where n is the word length (number of bits) of the address A) of the decoder 50 are connected to corresponding selection inputs of entry blocks 60-1 to 60-N, respectively.
An N-bit search key output Kout, an N-bit data output Dout, a search output Sout, an insert output INSout, a delete output DELout of the decoder 50 are connected to corresponding inputs of each of the entry blocks 60-1 to 60-N respectively.
The entry block 60-1 is provided with the following components:                An information storage part 61-1 that stores information as a search subject (hereinafter given a symbol “D-1” to indicate the relation with the entry block 60-1) and a binary validity bit V-1 indicating whether valid information D-1 as a search subject is held in the information storage part 61-1.        An AND gate 62-1 with its one input connected to one of the outputs of the information storage part 61-1 and its other input connected to the search output Sout, the one of the outputs corresponding to an output corresponding to the validity bit V-1 described above.        A comparator 63-1 (final stage of the entry block 60-1) that has an enable terminal being connected to the output of the AND gate 62-1 and that is connected to the described search key output Kout and to an output of the information storage part 61-1 corresponding to the information D-1 described above.        
The entry blocks 60-2 to 60-N have the same configuration as the entry block 60-1. The components of the entry blocks 60-2 to 60-N will be referred to by using the same reference symbols as the corresponding components of the entry block 60-1 except that the former will be given suffixes “2” to “N” though they are not shown in FIG. 5, and the description on them will be omitted.
The outputs of the comparators 63-1 to 63-N in the entry blocks 60-1 to 60-N are connected to corresponding inputs of a priority encoder 70 which outputs an associative address.
In the CAM having the above configuration, all the contents of the information storage parts 61-1 to 61-N are initialized when an apparatus incorporating the CAM is started. In the following description, it is assumed that the logical value of each of the validity bits V-1 to V-N is set to “1” only during a period when valid information is stored in its corresponding storage area.
Pieces of information D-1 to D-N are registered in the information storage parts 61-1 to 61-N in the following manner. Note that In the following description an item common to the information storage parts 61-1 to 61-N will be given a suffix “C” meaning that it may be any of suffixes “1” to “N”.
The decoder 50 performs the following processings in a period when an instruction I meaning “writing”(=“insert”) is supplied externally:                Decodes an address A-C that is input together with the instruction I, and selects only a single entry block 60-C corresponding to the address A-C from the entry blocks 60-1 to 60-N.        Writes, to the information storage part 61-C, a validity bit V-C having a logical value “1” and information D-C supplied from exterior, in synchronism with a control signal I/D indicating an instance at which data is written and being supplied along with the instruction I and the address A-C at an instant when a setup time of the information D-C and a priority rank P-C has been secured.        
For deletion of valid information D-C written to the information storage part 61-C for example, the information D-C is nullified in the following manner.
The decoder 50 performs the following processings in a period when an instruction I meaning “deletion”(=“delete”) is supplied externally:                Decodes an address A-C that is input together with the instruction I, and selects only a single entry block 60-C corresponding to the address A-C from the entry blocks 60-1 to 60-N.        Sets the logical value of the validity bit V-C registered in the information storage part 61-C to “0”, in synchronism with a control signal I/D that is supplied at an instant when a setup time for the instruction I and the address A-C has been secured.        
An address (associative address) of a storage area storing the same information as an externally supplied search key K, for example, is searched from the storage areas of the information storage parts 61-1 to 61-N in the following manner.
In a period when an instruction I meaning “search” (=“search”) is supplied externally, the decoder 50 supplies all the entry blocks 60-1 to 60-N with a search key K that is input externally in parallel with the instruction I.
In the entry block 60-C, the AND gate 62-C allows the comparator 63-C to operate only during a period when the instruction I (=search) is supplied and the logical value of the validity bit V-C stored in the information storage part 61-C is equal to “1”.
During this period, the comparator 63-C EXCLUSIVE-ORs between the information D-C stored in the information storage part 61-C together with the validity bit V-C (=“1”) and the search key K supplied from the decoder 50, and outputs binary information indicating whether all the bits of the EXCLUSIVE-OR result have a logical value “0” (for the sake of simplicity, it is assumed that its logical value is set to “1” only when the judgment result is “true”).
Among pieces of binary information having a logical value “1” and outputted in parallel from the comparators 63-1 to 63-N (i.e., entry blocks 60-1 to 60-N), the priority encoder 70 preferentially decodes a piece of binary information that is output from a comparator with the smallest suffix number, thereby outputting, as an associative address, a unique address that is given to a single storage area (one of the storage areas of the information storage parts 61-1 to 61-N) where the same information as the search key K is stored (e.g., refer to Japanese Unexamined Patent Publication Application Nos. Hei11-102589 (paragraphs 0003–0010) and 2001-236790).
In the meantime, in a case where the above conventional example is applied to filtering or routing of a router or the like, the same information as a search key K is often stored in a plurality of ones of the storage areas in the information storage parts 61-1 to 61-N.
In an Layer-3 switch, however, a port number, an IP address and a MAC address are input as a search key K and given priority in this input order, and a flow control may be performed according to a combination of part of the port number, the IP address, and the MAC address. Therefore, one or both of the IP address and the MAC address, when not included in the combination, are generally excluded from a subject of comparison with the contents of the information storage part 61-C according to a predetermined mask pattern.
That is, in such an Layer-3 switch, in the case where all combinations of the above kind are registered in the respective information storage parts 61-1 to 61-N, it is probable that a plurality of entries match with a search key K (hereinafter referred to as “multiple hit”) during a searching process (described above).
Therefore, a normal flow control is not always performed unless pairs of information as a subject of comparison and a mask pattern are registered in the information storage parts 61-1 to 61-N in proper order in which the above-mentioned priority order is attained.
For assuring such order, the larger the number N of the entry blocks 60-1 to 60-N and the number of flows to be controlled in parallel, the more complexing the managing of the permutation of pieces of information to be registered in the entry blocks 60-1 to 60-N. This means that enormous amount of processings is required for obtaining a proper permutation, and furthermore, it is likely that the higher the frequency at which the proper permutation is obtained, the lower the service quality and the transmission quality. Further, the more various the forms of a QoS (quality of service) control that is performed during the course of a flow control (described above), the higher the frequency, and the frequency also increases as the QoS control is done under load distribution.
A multiple hit (mentioned above) may also occur not only in the Layer-3 switch but also in an Layer-4 switch or Layer-7 switch, for example. The Layer-4 switch distributes packets and other requests issued from clients to proper servers according to the contents of headers that comply with a transport layer and the Layer-7 switch realizes contents distribution based on layered URL referencing, a transparent caching function, fail over, etc.